package com.xsomnus.data_structures.lru;

import java.util.HashMap;

/**
 * @author 叶小夏
 * @since 2019-08-30 10:34
 * Least Recently Use(最近最少使用)
 */
public class LruCache<K, V> {

    private final int MAX_CACHE_SIZE;
    private Entry<K, V> head;
    private Entry<K, V> tail;
    private HashMap<K, Entry<K, V>> cache;
    private EvictedListener<K, V> evictedListener;

    public LruCache() {
        this(8, null);
    }

    public LruCache(int MAX_CACHE_SIZE, EvictedListener<K, V> evictedListener) {
        this.MAX_CACHE_SIZE = MAX_CACHE_SIZE;
        this.cache = new HashMap<>();
        this.evictedListener = evictedListener;
    }

    public V get(K key) {
        Entry<K, V> entry = getEntry(key);
        if (entry == null) {
            return null;
        }
        moveToHead(entry);
        return entry.value;
    }


    public void remove(K key) {
        Entry<K, V> entry = getEntry(key);
        if (entry != null) {
            if (entry == head) {
                Entry<K, V> next = head.next;
                head.next = null;
                head = next;
                head.pre = null;
            } else if (entry == tail) {
                Entry<K, V> pre = tail.pre;
                tail.pre = null;
                tail = pre;
                tail.next = null;
            } else {
                entry.pre.next = entry.next;
                entry.next.pre = entry.pre;
            }
            cache.remove(key);
        }
    }


    public void put(K key, V value) {
        Entry<K, V> entry = cache.get(key);
        if (entry == null) {
            // 如果容量已经满了， 需要移除最后的节点
            if (cache.size() >= MAX_CACHE_SIZE) {
                cache.remove(tail.key);
                if (evictedListener != null) {
                    evictedListener.onEvicted(tail.key, tail.value);
                }
                removeTail();
            }

            entry = new Entry<>(key, value);
            moveToHead(entry);
            cache.put(key, entry);
        }
    }

    private void moveToHead(Entry<K, V> entry) {
        if (entry == head) {
            return;
        }

        if (head == null || tail == null) {
            head = tail = entry;
            return;
        }

        head.pre = entry;
        entry.next = head;
        entry.pre = null;
        head = entry;

    }

    private void removeTail() {
        if (tail != null) {
            Entry<K, V> prev = tail.pre;
            if (prev == null) {
                head = null;
                tail = null;
            } else {
                tail.pre = null;
                tail = prev;
                tail.next = null;
            }
        }
    }


    private Entry<K, V> getEntry(K key) {
        return cache.get(key);
    }

    // 双向链表
    private static class Entry<K, V> {
        Entry<K, V> pre;
        Entry<K, V> next;
        K key;
        V value;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }


    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        Entry<K, V> entry = head;
        while (entry != null) {
            stringBuilder.append(String.format("%s:%s ", entry.key, entry.value));
            entry = entry.next;
        }
        return stringBuilder.toString();
    }

}
